package com.lw.leetcode.sort.b;

import java.util.ArrayList;
import java.util.List;

/**
 * sort
 * 229. 求众数 II
 *
 * @Author liw
 * @Date 2021/6/28 17:10
 * @Version 1.0
 */
public class MajorityElement {

    public static void main(String[] args) {
        MajorityElement test = new MajorityElement();
        int[] arr = {1,2};
        List<Integer> integers = test.majorityElement(arr);


        System.out.println(integers);
    }




    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>(2);
        int x = 0;
        int y = 0;
        int cx = 0;
        int cy = 0;
        for (int num : nums) {
            if ((cx == 0 || num == x) && num != y) {
                ++cx;
                x = num;
            } else if (cy == 0 || num == y) {
                ++cy;
                y = num;
            } else {
                --cx;
                --cy;
            }
        }
        cx = 0;
        cy = 0;
        for (int num : nums) {
            if (x == num) {
                ++cx;
            } else if (y == num) {
                ++cy;
            }
        }
        if (cx > nums.length / 3) {
            list.add(x);
        }
        if (cy > nums.length / 3) {
            list.add(y);
        }
        return list;
    }

}
